package org.lintcode_Pattern;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-22:55
 * @Description:
 * 使用条件
 * • 找满足某个条件的所有方案 (99%)
 * • 二叉树 Binary Tree 的问题 (90%)
 * • 组合问题(95%)
 * ￮ 问题模型：求出所有满足条件的“组合”
 * ￮ 判断条件：组合中的元素是顺序无关的
 * • 排列问题 (95%)
 * ￮ 问题模型：求出所有满足条件的“排列”
 * ￮ 判断条件：组合中的元素是顺序“相关”的。
 * 不要用 DFS 的场景
 * 17. 连通块问题（一定要用 BFS，否则 StackOverflow）
 * 18. 拓扑排序（一定要用 BFS，否则 StackOverflow）
 * 19. 一切 BFS 可以解决的问题
 * 复杂度
 * • 时间复杂度：O(方案个数 * 构造每个方案的时间)
 * ￮ 树的遍历 ： O(n)
 * ￮ 排列问题 ： O(n! * n)
 * ￮ 组合问题 ： O(2^n * n)
 * 炼码例题
 * • LintCode 67.二叉树的中序遍历(遍历树)
 * • LintCode 652.因式分解(枚举所有情况)
 * @version: 1.0
 */
public class A7深度优先搜索DFS {

	public class DFSTemplate {

//		public ReturnType dfs(参数列表) {
//			// 递归出口条件，具体条件根据问题确定
//			if (递归出口) {
//				// 记录答案，具体记录方式根据问题确定
//				记录答案;
//				return;
//			}
//
//			// 进行当前状态或参数的处理，可能涉及到一些变量的计算或更新
//			// ...
//
//			// 遍历所有的拆解可能性，具体可能性根据问题确定
//			for (所有的拆解可能性) {
//				// 修改参数，为递归调用准备新的参数状态
//				修改所有的参数;
//
//				// 进行递归调用，深入探索当前的可能性
//				dfs(参数列表);
//
//				// 还原所有被修改过的参数，以便于探索其他可能性
//				还原所有被修改过的参数;
//			}
//
//			// 返回值，具体返回值根据问题确定。在很多情况下，DFS不需要返回值，
//			// 因为答案可能已经在过程中被记录或更新。但在分治算法中，通常需要返回值。
//			return something;
//		}

		// 其他辅助方法或类成员变量的声明
		// ...
	}

// ReturnType 是返回值的类型，根据具体问题可能是 int, boolean, List, TreeNode 等。
// 参数列表 是传递给 dfs 方法的参数，可以是节点、索引、数组等，具体根据问题确定。
// 记录答案可能是将结果存入一个列表、变量或者输出等，具体根据问题确定。
// 修改参数是为下一次递归调用准备，可能涉及到状态的更新或新状态的创建。
// 还原参数是为了在探索完当前路径后，能够回到上一个状态点继续探索其他可能。
}
